package org.example.day03;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <div>  给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，如[0, 1]表示从0到1的路径。每个节点用正整数表示。求这个数据的首节点与尾节点，题目给的用例会是一个首节点，但可能存在多个尾节点。同时，图中可能含有环。如果图中含有环，返回[-1]。 </div> <div>  说明：入度为<span>0</span>是首节点，出度为<span>0</span>是尾节点。<br> </div> <div>  <img alt="" src="https://uploadfiles.nowcoder.com/images/20200704/329232_1593849230510_F7F0BBDB094D0B83D7561FC5EC2130D7"><br> </div> <div>  <br> </div> <div>  <br> </div>
 *
 * 给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，
 * 如[0, 1]表示从0到1的路径。每个节点用正整数表示。求这个数据的首节点与尾节点，题目给的用例会是一个首节点，但可能存在多个尾节点。
 * 同时，图中可能含有环。如果图中含有环，返回[-1]。
 * 说明：入度为0是首节点，出度为0是尾节点。
 *
 *
 * @date 2024/3/11 15:22
 */
public class test059 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 读取输入的键值对数量
        int[] edges = new int[2 * N];
        for (int i = 0; i < 2 * N; i++) {
            edges[i] = scanner.nextInt(); // 读取键值对，转换成整数数组
        }

        List<int[]> pairs = new ArrayList<>();
        for (int i = 0; i < 2 * N; i += 2) {
            pairs.add(new int[]{edges[i], edges[i + 1]}); // 将输入转换成[start, end]形式的数组列表
        }

        int[] result = findStartAndEndNodes(pairs); // 找到首节点和尾节点

        for (int node : result) {
            System.out.print(node + " "); // 打印结果
        }
    }

    public static int[] findStartAndEndNodes(List<int[]> pairs) {
        Map<Integer, Integer> indegrees = new HashMap<>(); // 记录每个节点的入度
        Map<Integer, Integer> outdegrees = new HashMap<>(); // 记录每个节点的出度
        Set<Integer> allNodes = new HashSet<>(); // 记录图中所有节点

        for (int[] pair : pairs) {
            int start = pair[0];
            int end = pair[1];
            outdegrees.put(start, outdegrees.getOrDefault(start, 0) + 1); // 增加起始节点的出度
            indegrees.put(end, indegrees.getOrDefault(end, 0) + 1); // 增加结束节点的入度
            allNodes.add(start); // 添加起始节点到节点集合
            allNodes.add(end); // 添加结束节点到节点集合
        }

        int startNode = -1; // 首节点
        List<Integer> endNodes = new ArrayList<>(); // 尾节点列表
        for (int node : allNodes) {
            if (!indegrees.containsKey(node)) { // 如果节点没有入度，说明是首节点
                if (startNode == -1) {
                    startNode = node;
                } else {
                    return new int[]{-1}; // 如果找到多于一个的首节点，则图有问题，返回[-1]
                }
            }
            if (!outdegrees.containsKey(node)) { // 如果节点没有出度，说明是尾节点
                endNodes.add(node);
            }
        }

        if (startNode == -1 || endNodes.isEmpty()) { // 如果没有找到首节点或尾节点，返回[-1]
            return new int[]{-1};
        }

        if (hasCycle(allNodes, pairs)) { // 如果图中存在环，则返回[-1]
            return new int[]{-1};
        }

        Collections.sort(endNodes); // 对尾节点列表进行排序

        int[] result = new int[endNodes.size() + 1];
        result[0] = startNode; // 第一个元素是首节点
        for (int i = 0; i < endNodes.size(); i++) {
            result[i + 1] = endNodes.get(i); // 后续元素是尾节点列表
        }

        return result; // 返回首节点和尾节点数组
    }

    public static boolean hasCycle(Set<Integer> allNodes, List<int[]> pairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>(); // 构建图，使用邻接表表示
        for (int[] pair : pairs) {
            int start = pair[0];
            int end = pair[1];
            if (!graph.containsKey(start)) {
                graph.put(start, new ArrayList<>());
            }
            graph.get(start).add(end); // 添加边到图中
        }

        Set<Integer> visited = new HashSet<>(); // 用于标记已访问的节点
        Set<Integer> recStack = new HashSet<>(); // 用于记录当前递归调用堆栈中的节点

        for (int node : allNodes) {
            if (!visited.contains(node)) {
                if (dfs(node, graph, visited, recStack)) { // 使用深度优先搜索检查是否存在环
                    return true; // 如果存在环，返回true
                }
            }
        }

        return false; // 如果不存在环，返回false
    }

    public static boolean dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited, Set<Integer> recStack) {
        visited.add(node);
        recStack.add(node);

        if (graph.containsKey(node)) {
            for (int neighbor : graph.get(node)) { // 对当前节点的所有邻接节点进行深度优先搜索
                if (!visited.contains(neighbor)) {
                    if (dfs(neighbor, graph, visited, recStack)) {
                        return true; // 如果存在环，返回true
                    }
                } else if (recStack.contains(neighbor)) {
                    return true; // 如果当前节点已经在递归调用堆栈中，说明存在环，返回true
                }
            }
        }

        recStack.remove(node);
        return false; // 如果没有环，返回false
    }
}

